/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    /*
    先对两个链表进行翻转
    分别取出第一个元素中的值，进行相加存放sum中
    如果sum大于=10需要进位，用cnt表示要进多少位
    头插法创建新结点，新节点的值为sum%10
    最后两个链表都遍历完成后，如果cnt>0
    再创建一个新结点，此时新节点的值为cnt
    头插法的方式加入
    */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        ListNode *h1=ReverseList(head1);
        ListNode *h2=ReverseList(head2);
        ListNode *res=nullptr;
        int cnt=0;
        while(h1||h2)
        {
            int x1=(h1==nullptr?0:h1->val);
            int x2=(h2==nullptr?0:h2->val);
            int sum=x1+x2+cnt;
            cnt=sum/10;
            ListNode *pnew=new ListNode(sum%10);
            pnew->next=res;
            res=pnew;
            
	//指针向前走
            h1=(h1==nullptr?nullptr:h1->next);
            h2=(h2==nullptr?nullptr:h2->next);
        }
        if(cnt>0)
        {
            ListNode *pnew=new ListNode(cnt);
            pnew->next=res;
            res=pnew;
        }
        return res;
    }
    //翻转链表
    ListNode *ReverseList(ListNode *head)
    {
       ListNode *pre=nullptr;
        auto p=head;
        ListNode *r;
        while(p)
        {
            r=p->next;
            p->next=pre;
            pre=p;
            p=r;
        }
        return pre;
    }
};